//给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。 
//
// 整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。 
//
// 返回被除数 dividend 除以除数 divisor 得到的 商 。 
//
// 注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−2³¹, 231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 2
//31 − 1 ；如果商 严格小于 -2³¹ ，则返回 -2³¹ 。 
//
// 
//
// 示例 1: 
//
// 
//输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = 3.33333.. ，向零截断后得到 3 。 
//
// 示例 2: 
//
// 
//输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。 
//
// 
//
// 提示： 
//
// 
// -2³¹ <= dividend, divisor <= 2³¹ - 1 
// divisor != 0 
// 
//
// Related Topics 位运算 数学 👍 1120 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution29
{

    public int divide(int dividend, int divisor) {
        int sign = isSameSign(dividend, divisor) ? 1 : -1;
        long dividend_long = Math.abs((long) dividend);
        long divisor_long = Math.abs((long) divisor);
        if (dividend_long < divisor_long) {
            return 0;
        }

        long res = 0;
        int i = 1;
        long tmp = divisor_long;
        while (dividend_long >= tmp) {
            dividend_long = dividend_long - (tmp);
            res += i;
            tmp = tmp << 1;
            i = i << 1;
        }

        long signedResult = res * sign;
        long rest;
        if (divisor_long > 0) {
            rest = divide((int)dividend_long, (int)divisor_long);
            signedResult += rest * sign;
        }

        if (signedResult > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (signedResult < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int) signedResult;
    }

    private static boolean isSameSign(int dividend, int divisor) {
        return ((dividend ^ divisor) >> 31 & 0x1) == 0;
    }
}


// Time Limit Exceeded
class Solution29_暴力
{
    public int divide(int dividend, int divisor) {
        int sign = isSameSign(dividend, divisor) ? 1 : -1;
        long dividend_long = Math.abs((long) dividend);
        long divisor_long = Math.abs((long) divisor);
        long res = 0;
        while (dividend_long >= divisor_long) {
            dividend_long = dividend_long - divisor_long;
            res++;
        }

        res = res * sign;
        if (res > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (res < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int) res;
    }

    private static boolean isSameSign(int dividend, int divisor) {
        return ((dividend ^ divisor) >> 31 & 0x1) == 0;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

class Test29 {
    public static void main(String[] args) {
        // int res = new Solution().divide(7, -3);
        // int res = new Solution().divide(10, 3);
        // int res = new Solution().divide(-2147483648, -1);
        // int res = new Solution().divide(2147483647, 3);
        // System.out.println(res);
    }
}